package Testdemo2;

import java.util.*;
/**
 * Created with IntelliJ IDEA.
 * Description:
 * User:周次煜
 * Date: 2024-05-06
 * Time：16:43
 */
public class Test7 {
    public static List<Integer> findSubstring(String s, String[] words) {

        List<Integer> list=new ArrayList<>();
        Map<String, Integer> map1=new HashMap<>();

        // 挑选字符的大小
        int sz=s.length();

        // 目标字符串数组的总长度
        int wz=words.length;

        //目标字符的长度
        int ws=words[0].length();

        for(int i=0 ; i< wz ; i++) {
            // 将 目标字符 进入到 map1
            String ch=words[i];
            if(map1.containsKey(ch)) {
                map1.put(ch,map1.get(ch)+1);
            } else {
                map1.put(ch,1);
            }
        }

        // 将 挑选字符进入到 map2 中

        int left=0,right=wz*ws-1;

        while(right < sz) {
            Map<String,Integer> map2= new HashMap<>();
            int left1=left;
            int right1=left+ws-1;

            while(right1 <= right) {
                String tmp= s.substring(left1,right1+1);
                if(map2.containsKey(tmp)) {
                    map2.put(tmp,map2.get(tmp)+1);
                } else {
                    map2.put(tmp,1);
                }
                left1 += ws;
                right1 = left1 + ws -1;
            }

            if(map2.equals(map1)) {
                list.add(left);
            }
            left++;
            right++;
            map2.clear();
        }

        return list;
    }

    public static void main1(String[] args) {
        String[] strings={"foo","bar"};
        System.out.println(findSubstring("barfoothefoobarman", strings));
        Map<Integer,Integer> map1=new HashMap<>();
        map1.put(1,2);
        map1.put(3,4);
        map1.put(5,6);

        Map<Integer,Integer> map2= Map.copyOf(map1);
        System.out.println(map2);

    }

//    public static String minWindow(String s, String t) {
//        int sz=s.length();
//        int tz=t.length();
//        Map<Character,Integer> map1= new HashMap<>();
//
//        //将目标字符串 进入 map1 中
//        for(int i=0; i < tz ; i++) {
//            char ch=t.charAt(i);
//            if(map1.containsKey(ch)) {
//                map1.put(ch,map1.get(ch)+1);
//            } else {
//                map1.put(ch,1);
//            }
//        }
//
//        // 将目标 map 拷贝一份进行检查
//        Map<Character,Integer> map2= new HashMap<>(map1);
//        int left1=0,right1=0;
//        int len = Integer.MAX_VALUE;
//        for(int left=0,right=0; right <sz ; right++) {
//
//            // 先得到 某个字符进行判断
//            char ch=s.charAt(right);
//
//            // 存在的话就删除次数
//            if(map2.containsKey(ch)) {
//
//                // 进行入窗口
//                map2.put(ch,map2.get(ch)-1);
//
//                // 一旦次数为 0 就删除该 key
//                if(map2.get(ch) <= 0) {
//                    map2.remove(ch);
//                }
//            }
//
//            // 一但出现结果为 大小空 说明 全部找到
//            if(map2.isEmpty()) {
//
//                // 如果这个子字符串长度小于前面的最小值
//                if(right-left+1 < len) {
//                    len=right-left+1;
//
//                    // 记录好前面的下标
//                    left1=left;
//                    right1=right;
//                }
//
//                // 再拷贝一份进行再次判断
//                map2= new HashMap<>(map1);
//
//                // 进行出窗口操作
//                while(!map2.containsKey(s.charAt(left))) {
//                    left++;
//                }
//            }
//
//        }

//        // 截断字符串
//        return s.substring(left1,right1+1);
//    }
        public static String minWindow(String s, String t) {

        // 先得到两个字符串的长度
        int slength=s.length();
        int  tlength=t.length();


        // 先定义两个数组来哈希映射 统计次数
        int [] hash1= new int[52];
        int [] hash2= new int[52];

        // 先统计 s 中 字符的个数
        for(int i=0; i < tlength ; ++i) {
            hash1[t.charAt(i)-'A']++;
        }

        int len = Integer.MAX_VALUE;
        int begin=Integer.MAX_VALUE;
        // 进行滑动窗口操作
        for(int left=0,right=0, count=0; right < slength ; right++) {
            // 入窗口
            char in= s.charAt(right);
            hash2[in-'A']++;

            // 判断
            if(hash2[in-'A'] <= hash1[in-'A']) {
                count++;
            }

            // 更新结果
            while(count == tlength) {

                // 得到最小长度 并记录起始位置
                if(right-left+1 < len) {
                    begin=left;
                    len=right-left+1;
                }

                char out= s.charAt(left);
                // 出窗口
                if(hash2[out-'A'] <= hash1[out-'A']) {
                    count--;

                }

                hash2[out-'A']--;
                left++;
            }
        }

        if(begin==Integer.MAX_VALUE) return "";

        // 截断时要注意 左闭右开
        // 当起始位置加上 字符串长度时
        // 不需要 -1

        return s.substring(begin,begin+len);
        }

    public static void main4(String[] args) {
        System.out.println(minWindow("ADOBECODEBANC", "ABC"));

    }

    public static void main3(String[] args) {
        Map<Integer,Integer> map1=new HashMap<>();
        map1.put(1,2);
        map1.put(3,4);
        map1.put(5,6);


        Map<Integer,Integer> map2= Map.copyOf(map1);
        System.out.println(map2);
        map2.put(1,10);
    }

    public static void main5(String[] args) {
        String[] words = {"word","good","best","good"};
        System.out.println(findSubstring1("wordgoodgoodgoodbestword", words));
    }

    public static List<Integer> findSubstring1(String s, String[] words) {

        // 得到每个 字符串以及字符串数组的长度
        int slen=s.length();
        int wdslen=words.length;
        int wlen= words[0].length();



        // 定义一个返回结果
        List<Integer> ret= new ArrayList<>();

        // 先 定义两个 hashMap
        // 用于统计 字符串 的数量
        Map<String, Integer>  hash1= new HashMap<>();


        // 统计 words 里面 的长度
        for(int i=0; i< wdslen ; i++) {
            String str= words[i];
            hash1.put(str,hash1.getOrDefault(str,0)+1);
        }


        // 开始进行滑动窗口操作
        for(int j=0; j < wlen ; ++j) {

            Map<String, Integer>  hash2= new HashMap<>();
            // 初始化 left 和 right 的最初位置
            int  left=j;
            int right= j + wlen;
            int count=0;
            // 设置  right 每次跳跃的 跨度
            for( ;right  <= slen ; right += wlen) {

                // 通过入窗口操作
                String in = s.substring(right-wlen,right);

                hash2.put(in,hash2.getOrDefault(in,0)+1);

                // 判断有效结果
                if(hash1.containsKey(in) && hash2.get(in).compareTo(hash1.get(in)) <= 0) {
                    count++;
                }

                // 判断是否存在
                while(count >= wdslen) {

                    // 更新结果
                    if(right-left ==  wdslen * wlen) {
                        ret.add(left);
                    }

                    String out= s.substring(left,left+wlen);
                    // 出窗口操作
                    if(hash1.containsKey(out) && hash2.get(out).compareTo(hash1.get(out)) <= 0) {
                        count--;
                    }

                    // 更新每次 left 跳跃的值
                    hash2.put(out,hash2.get(out)-1);
                    left += wlen;
                }
            }

        }

        return ret;

    }

    public static void main(String[] args) {
        int[]nums={-1,0,3,5,9,12};

        System.out.println(search(nums, 9));
    }

    public static int search(int[] nums, int target) {
        int numslen = nums.length;
        int left=0,right=numslen-1;
        while(left <= right) {
            int mid= left + ((right - left) >>> 1 );
            if(nums[mid] > target) {
                right = mid - 1;
            } else if(nums[mid] < target ) {
                left = mid + 1;
            } else {
                return mid;
            }
        }

        return -1;
    }
}
